package com.stillcoolme.leetcode.algorithm.divideconquer;

/**
 * <p>求 最大的子数组 和</p>
 *
 * 分治法：
 *  1. 分成计算 左边最大 t1、右边最大 t2、以中点向左右两边取最大 t3  3部分
 *  2. 关键在于中间怎么切？  0 + len / 2 = mid, 得到中点，分为  [0，mid)、[mid, len) 遵循 左开右闭
 *  3. 递归终点：因为 左开右闭，所以当 left、start 相差为 1 的时候就是只有一个元素了，就返回
 * @author zhangjianhua
 * @version V1.0.0
 * @date 2023/10/10 22:51 周二
 */
public class lc0053_MaxSubarray {

    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return find(nums, 0, nums.length);
    }

    private int find(int[] nums, int left, int right) {
        if (right - left == 1) {
            return nums[left];
        }
        int middle = (left + right) / 2;
        // 得到左边最大的 t1
        int t1 = find(nums, left, middle);
        // 得到右边最大的 t2
        int t2 = find(nums, middle, right);

        // 开始获取中间最大的t3

        // 以中间为起点，向左边得到t3a
        int t3a = Integer.MIN_VALUE;  //保存中点左边的最大值，不包含中点 !!
        int sum = 0;
        for (int start = middle - 1; start >= left; start --) {
            sum += nums[start];
            if (sum > t3a) {
                t3a = sum;
            }
        }
        // 以中间为起点，向左边得到t3b
        int t3b = Integer.MIN_VALUE;
        sum = 0;
        for (int start = middle; start < right; start ++) {
            sum += nums[start];
            if (sum > t3b) {
                t3b = sum;
            }
        }

        int t3 = t3a + t3b;

        int max = t3;
        if (t1 > max) max = t1;
        if (t2 > max) max = t2;
        return max;
    }


    public static void main(String[] args) {
        lc0053_MaxSubarray lc0053_maxSubarray = new lc0053_MaxSubarray();
        int[] nums = new int[]{1};
        int max = lc0053_maxSubarray.maxSubArray(nums);
        System.out.println(max);

    }
}
